EGR vacuum is good? I'm assuming the '96 system works similar as earlier years -- that is, has an electrically controlled vacuum valve? Could be as simple as a bad electrical connection too?
If valve solenoid is bad - could try putting a resistor across the harness connector. ECU would then think the solenoid is good?